前面
说了一大堆杂七杂八的东西，今天换一换，简单总结一下STL——但是不考虑新的C++11标准，无它，用的不多，不熟。虽然多少知道一些新标准里面的东西是怎么一回事：比如左值右值，λ表达式，类型推导等，也不是不会用，但怎么用好则又是一回事情。就像OS与网络，虽然并非对其一无所知，且并不忌惮，但一直没有进行太多投入。因为我个人觉得这些都是属于系统编程的，相较之下工程意味更重，去公司锻炼事半功倍，不似图形或者编译这种需要有理论撑起来的，搞不清就是搞不清。
当然，我本人并无一丝对OS，网络的轻视之意。此二者之难，难在它们把现实中遇到的各种复杂问题的解决方案放到一个系统中行了巧妙的解决，是集多年以来经验之大成者。在学习过程中，“这么做就是为了解决这个问题的！”，此种想法不止一次出现过——当然，也很有可能是我自己见识尚浅，自以为是。
上面想法是在我大致学习了MIT的JOS之后形成的。虽然曾经跟了MIT JOS 2014实验课的几个关键Labs，但放下的时间稍嫌久了些，竟是没有剩下许多印象——然而终归有迹可循，日后想要重新拿起，想来应该不会无从下手。
正文
谈到STL，便不能不谈到泛型编程与Iterator模式。
CPP泛型编程的基础已经在首篇的《View CPP Template》里面演示过了，这里不再多说。这里主要说一下Iterator模式以此作为“设计模式”这 个话题的补充，并说明其在STL中的应用。
迭代器模式
事实上，迭代器模式是通过增加一个迭代器层来实现数据与算法分离的。例如在STL中，对于vector和list的遍历都可以通过：
1
2
3
4
| for(auto it = container.begin(); it != container.end();++it)
{
}
|
来完成（当然使用for_each也可），而众所周知vector是一个使用了变长数组的容器而list则是一个使用了双向链表的容器，两者的数据存储方式完全不同。
接下来就用一个固定长度的数组与一个链表来简单演示一下通常情况下的迭代器模式（不将Iterator类作为嵌套类的原因是为了更凸显“加一层”的做法，下面的代码实际不可取！）。
首先，定义一个如下的数组与链表，并初始化：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #define ARRAY_LEN 5
int myArray[5] = {5,4,3,2,1};
struct ListNode
{
int m_data;
ListNode* m_next;
ListNode(int data, ListNode* next):m_data(data),m_next(next)
{
}
};
ListNode n1(9,NULL);
ListNode n2(8,&n1);
ListNode n3(7,&n2);
ListNode n4(6,&n3);
ListNode n5(5,&n4);
|
接下来定义迭代器：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| struct Iterator
{
void* m_ptr;
virtual void operator++() = 0;
virtual char* end() = 0;
virtual int* operator*() = 0;
virtual char* iterator() = 0;
};
struct ArrayIterator :public Iterator
{
ArrayIterator(int* array)
{
m_ptr = (void*)array;
}
virtual void operator++()
{
int* ptr = (int*)m_ptr;
ptr++;
m_ptr = (void*)ptr;
}
virtual char* end()
{
return (char*)(myArray+ARRAY_LEN);
}
virtual int* operator*()
{
return (int*)m_ptr;
}
virtual char* iterator()
{
return (char*)m_ptr;
}
};
struct ListIterator :public Iterator
{
ListIterator(ListNode* head)
{
m_ptr = (void*)head;
}
virtual void operator++()
{
ListNode* ptr = (ListNode*)m_ptr;
ptr = ptr->m_next;
m_ptr = (void*)ptr;
}
virtual char* end()
{
return NULL;
}
virtual int* operator*()
{
ListNode* ptr = (ListNode*)m_ptr;
return &ptr->m_data;
}
virtual char* iterator()
{
return (char*)m_ptr;
}
};
|
最后定义一个只与Iterator相关的遍历算法：
1
2
3
4
5
6
7
| void printAll(Iterator& it)
{
for (; it.iterator() != it.end(); ++it)
{
std::cout << * (* it) << std::endl;
}
}
|
至此，我们可以这样来输出数组和链表中的内容：
1
2
3
4
5
6
7
8
9
10
| ArrayIterator arrayIt(myArray);
ListIterator listIt(&n5);
int main(int argc, char** argv)
{
std::cout << "Array:" << std::endl;
printAll(arrayIt);
std::cout << "List:" << std::endl;
printAll(listIt);
return 0;
}
|
再次重申，上述代码很差，仅为说明思想。
其实加一层实际上是为了能够为上层统一接口，这一思想在实际应用十分常见。例子中，对于存储方式迥异的数组和链表加了一个迭代器层之后就可以使用同一个方法对其进行遍历了。
那么，STL中的迭代器模式有是如何的呢？
STL Iterator
其实理解了迭代器模式，再加上前面博文中对C++ Template的讲述，STL中的迭代器已经很好理解了。
回看上面的例子，我们可以整理出一下信息：两个不同的存储类型（array， list）；两个不同类型的迭代器（array iterator，list iterator）；迭代器与存储类型的紧耦合性。
然后回顾Template的核心：类型运算。
接着说STL中的迭代器。还是上代码吧，一个小例子，还是以vector和list为主的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
| #include <iostream>
template <typename T>
struct MyVector
{
private:
T* m_array;
int m_size;
int m_cap;
public:
MyVector()
{
m_array = NULL;
m_size = 0;
m_cap = 0;
}
typedef T* iterator;
iterator begin()
{
return m_array;
}
iterator end()
{
return (m_array + m_size);
}
void push_back(T&& t)
{
if (m_array == NULL)
{
m_array = new T[2];
m_cap = 2;
}
else if (m_size == m_cap)
{
m_cap *= 2;
T* A = new T[m_cap];
for (int i = 0; i < m_size; ++i)
{
A[i] = m_array[i];
}
delete[] m_array;
m_array = A;
}
m_array[m_size] = t;
m_size++;
}
};
template <typename T>
struct MyList
{
private:
struct Node
{
T m_data;
Node* m_next;
};
Node* m_head;
Node* m_tail;
public:
MyList()
{
m_head = NULL;
m_tail = NULL;
}
struct iterator
{
Node* m_ptr;
iterator(Node* n)
{
m_ptr = n;
}
void operator++()
{
m_ptr = m_ptr->m_next;
}
T operator*()
{
return m_ptr->m_data;
}
bool operator!=(iterator& it)
{
return this->m_ptr != it.m_ptr;
}
};
iterator begin()
{
return iterator(m_head);
}
iterator end()
{
return iterator(NULL);
}
void push_back(T&& t)
{
if (m_head == NULL)
{
m_head = new Node;
m_head->m_data = t;
m_head->m_next = NULL;
m_tail = m_head;
}
else
{
Node* n = new Node;
n->m_data = t;
n->m_next = NULL;
m_tail->m_next = n;
m_tail = n;
}
}
};
MyVector<int> myArray;
MyList<int> mylist;
int main(int argc, char** argv)
{
myArray.push_back(0);
myArray.push_back(1);
myArray.push_back(2);
myArray.push_back(3);
myArray.push_back(4);
mylist.push_back(9);
mylist.push_back(8);
mylist.push_back(7);
mylist.push_back(6);
mylist.push_back(5);
std::cout << "Array:" << std::endl;
for (auto it = myArray.begin(); it != myArray.end(); ++it)
{
std::cout << (* it) << std::endl;
}
std::cout << "List:" << std::endl;
for (auto it = mylist.begin(); it != mylist.end(); ++it)
{
std::cout << (* it) << std::endl;
}
return 0;
}
|
代码为了突出迭代器而简化了很多，但个人觉得说明STL里面的迭代器已经差不多足够了。
从上面也可以看出来，实际上迭代器并非仅仅是一个指针或者而已，如同所谓的“引用”——“引用（Reference）”会在后面的文里面涉及到，如果不出意外应该是会被归在“编译相关”的文章里面而不是在CPP相关的文章中。
现在也可以理解为什么标准库中的sort方法采用的是归并而不是快排了——快排作为对数据储存形式依赖严重的排序算法，显然不适合。
结束
本文算是图形编译说了一堆之后的“偷闲”文。有了上面的铺垫，再去看旧标准的STL应该会清晰很多。
至于新标准，给我个人的感觉就是：那些个曾经高贵冷艳（或者说很多时候认为不知道也不影响写程序）的理论距离C++程序员越来越近了！由于我没怎么用过Boost库，所以从C++03到C++11的过渡对我而言并非很平滑。后面肯定继续会有对新标准（其实已经是出了五年的“旧标准”了）的学习总结，不过应该是编译与CPP两边相互照应着进行了。